package gold.digger;

import org.apache.slider.common.tools.Comparators;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.TreeMap;
import java.util.stream.Collectors;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC218 {
    public long startExecuteTime = System.currentTimeMillis();


    /*
     * @param 此题目参考了别人代码
     * 这是因为问题情况较为复杂
     * 未来需要再次复习此道题目
     * 困难的扫描线问题
     * @return:
     */
    class Solution {
        public List<List<Integer>> getSkyline(int[][] bs) {
            List<List<Integer>> ans = new ArrayList<>();

            // 预处理所有的点，为了方便排序，对于左端点，令高度为负；对于右端点令高度为正
            List<int[]> ps = new ArrayList<>();
            for (int[] b : bs) {
                int l = b[0], r = b[1], h = b[2];
                ps.add(new int[]{l, -h});
                ps.add(new int[]{r, h});
            }

            // 先按照横坐标进行排序
            // 如果横坐标相同，则按照左端点排序
            // 如果相同的左/右端点，则按照高度进行排序
            Collections.sort(ps, (a, b) -> {
                if (a[0] != b[0]) return a[0] - b[0];
                return a[1] - b[1];
            });

            // 大根堆
            PriorityQueue<Integer> q = new PriorityQueue<>((a, b) -> b - a);
            int prev = 0;
            q.add(prev);
            for (int[] p : ps) {
                int point = p[0], height = p[1];
                if (height < 0) {
                    // 如果是左端点，说明存在一条往右延伸的可记录的边，将高度存入优先队列
                    q.add(-height);
                } else {
                    // 如果是右端点，说明这条边结束了，将当前高度从队列中移除
                    q.remove(height);
                }

                // 取出最高高度，如果当前不与前一矩形“上边”延展而来的那些边重合，则可以被记录
                int cur = q.peek();
                if (cur != prev) {
                    List<Integer> list = new ArrayList<>();
                    list.add(point);
                    list.add(cur);
                    ans.add(list);
                    prev = cur;
                }
            }
            return ans;
        }
    }

    class Solution_Complex_Thought {
//        public List<List<Integer>> getSkyline(int[][] buildings) {
//            List<List<Integer>> res = new ArrayList<>();
//            TreeMap<Integer, List<int[]>> heightMap = new TreeMap(Comparator.reverseOrder());
//            for (int[] building : buildings) {
//                int height = building[2], start = building[0], end = building[1];
//                if (!heightMap.containsKey(height)) heightMap.put(height, new ArrayList<>());
//                heightMap.get(height).add(new int[]{start, end});
//            }
//
//            // 从最高高度，开始合并区间
//            TreeMap<Integer, Integer> totalInterval = new TreeMap<>();
//            for (Integer height : heightMap.keySet()) {
//                TreeMap<Integer, Integer> curHeightInterval = new TreeMap<>();
//                for (int[] interval : heightMap.get(height)) {
//
//                }
//            }
//
//        }
//
//
//        public int[] mergeInterval(TreeMap<Integer, Integer> intervalMap, int start, int end) {
//            Integer leftSide = intervalMap.floorKey(start), rightSide = intervalMap.ceilingKey(start);
//
//            if (null == leftSide && null == rightSide) {
//                intervalMap.put(start, end);
//                return new int[]{start, end};
//            }
//
//            if (null == leftSide) {
//                if (end < rightSide.intValue()) {
//                    intervalMap.put(start, end);
//                    return new int[]{start, end};
//                } else {
//                    int rightSideEnd = intervalMap.get(rightSide);
//                    intervalMap.remove(rightSide);
//                    intervalMap.put(start, Math.max(end,rightSideEnd));
//                    continue;
//                }
//            }
//
//            if (null == rightSide) {
//                if (start > intervalMap.get(leftSide)) {
//                    intervalMap.put(start, end);
//                    continue;
//                } else {
//                    intervalMap.put(leftSide, end);
//                    continue;
//                }
//            }
//
//            // 两边都有，都需要考虑合并
//
//        }

    }

    public void run() {
        Solution solution = new Solution();
        List<Integer> list = new ArrayList<>();
        System.out.println(solution.toString());
    }

    public static void main(String[] args) throws Exception {
        LC218 an = new LC218();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
